// 最短路径 Dijkstra
// 教学视频 https://www.bilibili.com/video/BV1zz4y1m7Nq/?spm_id_from=333.788.recommend_more_video.-1&vd_source=4fd973d19cb5506a7c9f2d59e8ab5165

const { log, isNumber } = require('../commonTool/zddtool.js');

class NodeMatrix {
    constructor() {
        this.list = [];
    }

    add(node1, node2, value) {
        this.list.push(new NodeLink(node1, node2, value));
    }

    out() {
        return this.list;
    }
}

class NodeLink {
    constructor(node1, node2, value) {
        this.node1 = node1;
        this.node2 = node2;
        this.value = value;
    }

    hasNode(node) {
        if (!isNumber(node)) {
            return false;
        }

        return this.node1 === node || this.node2 === node;
    }

    linkNode(node) {
        if (!isNumber(node)) return null;

        if (this.node1 === node) {
            return this.node2;
        } else if (this.node2 === node) {
            return this.node1;
        }

        return null;
    }
}

class DijkstraNode {
    constructor(ID) {
        this.ID = ID;
        this.selected = false;
        this.minDist = Number.MAX_VALUE;
        this.parentID = -1;
    }
}

class Dijkstra {
    constructor(nodeList, startNode, endNode) {
        this.dijNodeList = [];
        this.startNode = startNode;
        this.endNode = endNode;

        this.sortNodeList(nodeList);
        this.initDijNodeList(); // 初始化prim列表
        this.init();

        log(`Dijkstra Init Complete`);
        log(JSON.stringify(this.out()));
    }

    out() {
        log(`[Shortest Rode]`);
        log(this.totalValue());

        return new Array(this.dijNodeList.length).fill(-1).map((_, idx) => {
            return {
                ID: this.dijNodeList[idx].ID,
                minDist: this.dijNodeList[idx].minDist,
            };
        });
    }

    totalValue() {
        if (this.dijNodeList.findIndex((ele) => !ele.selected) >= 0) return -1;

        return this.dijNodeList.find((ele) => ele.ID === this.endNode.ID)
            .minDist;
    }

    sortNodeList(nodeList) {
        // Dijkstra没必要排序了，就是第一个节点
        this.nodeList = nodeList;
        // this.nodeList.sort((a, b) => a.value - b.value);
    }

    initDijNodeList() {
        let arr = {};
        for (let ele of this.nodeList) {
            const { node1, node2 } = ele;
            [node1, node2].forEach((node) => {
                if (!arr[node]) {
                    arr[node] = 1;
                } else {
                    arr[node] += 1;
                }
            });
        }

        log(`[initDijNodeList]`);
        // log(arr);

        Object.keys(arr).forEach((key) => {
            this.dijNodeList.push(new DijkstraNode(parseInt(key)));
        });

        this.startNode = this.dijNodeList.find(
            (ele) => ele.ID === this.startNode
        );

        this.endNode = this.dijNodeList.find((ele) => ele.ID === this.endNode);

        log('startNode');
        log(JSON.parse(JSON.stringify(this.startNode)));

        log('endNode');
        log(JSON.parse(JSON.stringify(this.endNode)));
    }

    init() {
        // Dijkstra 出发点0
        let pNode = this.dijNodeList.find(
            (ele) => ele.ID === this.startNode.ID
        );

        pNode.minDist = 0;
        pNode.parentID = pNode.ID;

        for (let i = 0; i < this.nodeList.length; i++) {
            // 从prim中，挑选一个没有没选中的，但权值最低的节点
            let currentNode = this.dijNodeList
                .filter(
                    (ele) => !ele.selected && ele.minDist < Number.MAX_VALUE
                )
                .sort((a, b) => a.minDist - b.minDist)[0];

            if (currentNode == null) {
                log('error');
                log(this.out());
                break;
            }

            currentNode.selected = true;

            if (currentNode.ID === this.endNode.ID) {
                log(`[Dijkstra] Got to end node ${currentNode.ID}, loop break`);
                break;
            }

            // 更新当前节点的相邻节点的权值
            // 在矩阵中搜索当前节点的相邻节点
            let linkNodes = this.nodeList.filter((ele) =>
                ele.hasNode(currentNode.ID)
            );

            // 更新相邻节点的权值
            linkNodes.forEach((ele) => {
                let pNode = this.dijNodeList.find(
                    (pn) => pn.ID === ele.linkNode(currentNode.ID)
                );

                if (
                    !pNode.selected &&
                    pNode.minDist > ele.value + currentNode.minDist
                ) {
                    pNode.minDist = ele.value + currentNode.minDist;
                    pNode.parentID = currentNode.ID;
                }
            });
        }
    }
}

let matrix = new NodeMatrix();
matrix.add(0, 1, 4);
matrix.add(1, 2, 8);
matrix.add(2, 3, 7);
matrix.add(3, 4, 9);
matrix.add(4, 5, 10);
matrix.add(5, 6, 2);
matrix.add(6, 7, 1);
matrix.add(1, 7, 11);
matrix.add(7, 8, 7);
matrix.add(2, 8, 2);
matrix.add(6, 8, 6);
matrix.add(2, 5, 4);
matrix.add(3, 5, 14);
matrix.add(0, 7, 8);

let primIns = new Dijkstra(matrix.out(), 0, 4);
